//
//  215. 数组中的第K个最大元素（堆解法）.swift
//  Top600
//
//  Created by rjb on 2021/8/4.
//

import Foundation

class Solution215_2 {
    // 数组中的第k个最大元素
    // 可以采用小顶堆
    // 堆的大小为k，当小顶堆的元素超过k时，
    // 如果比堆顶元素大。则加入堆。
    // 如果比堆顶元素小。则不加入。
    func findKthLargest(_ nums:inout [Int], _ k: Int) -> Int {
        heapify(&nums, k)
        print(nums)
        return nums.first!
    }
    // 将元素进行堆化
    func heapify(_ nums: inout [Int], _ k: Int) {
        for i in 0..<nums.count {
            if i <= k {
                siftUp(&nums, index: i, k)
            } else {
                if nums[i] < nums.first! {
                    continue
                } else {
                    // 如果比堆顶元素要大，替换掉0堆顶，并将堆顶元素下沉
                    nums[0] = nums[i]
                    siftDown(&nums, index: 0, k)
                }
            }
        }
    }
    // 上滤
    // 不断的找比父节点小的元素进行交换
    // 最终确定位置填写进去就可以了
    func siftUp(_ nums: inout [Int], index: Int, _ k: Int) {
        var index = index
        let v = nums[index]
        while index > 0 {
            let pIndex = (index - 1) / 2
            let pv = nums[pIndex]
            // 当前值比父节点大，不做调整
            if v > pv {
                break
            }
            nums[index] = pv
            index = pIndex
        }
        nums[index] = v
    }
    // 下沉
    // 小顶堆元素下沉时，需要比较将左右子树比较小的数据放移到父节点
    func siftDown(_ nums: inout [Int], index: Int, _ k: Int) {
        let v = nums[index]
        var index = index
        while index < nums.count / 2 {
            let leftChild = index * 2 + 1
            let rightChild = leftChild + 1
            let cv = nums[leftChild]
            let rightcv = nums[rightChild]
            
            // 如果左边，右边都比v大，不需要处理
            if cv > v && rightcv > v {
                break
            }
            // 如果不是左边，右边都比v大，取较小的上移
            if rightcv < cv {
                nums[index] = rightcv
                index = rightChild
            } else {
                nums[index] = cv
                index = leftChild
            }
        }
        nums[index] = v
    }
    static func test() {
        let solution = Solution215_2()
        var nums = [3,2,3,1,2,4,5,5,6]
        let k = 4
        let result = solution.findKthLargest(&nums, k)
        print(result)
    }
}
